package com.leetcode;

/**
 * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 * 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。
 * 如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 * @author LZF
 */
public class L887鸡蛋掉落 {
	/**
	 * 思路：
	 * 1、确定N 和 F 的关系
	 * N 的定义：使用一栋从 1 到 N 共有 N 层楼的建筑
	 * F 的定义：满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破
	 * 因此得知，F 比 N 多一个 0 层
	 * 2、问题转换
	 * 将问题从： N 个楼层，有 K 个蛋，求最少要扔 T 次，才能保证当 F 无论是 0 <= F <= N 中哪个值，都能测试出来
	 * 转变为：有 K 个蛋，扔 T 次，求可以确定 F 的个数，然后得出 N 个楼层，
	 * 因此只要满足求得的F >= N + 1,返回T；否则T不断增一求F
	 * 3、通过扔蛋测试，怎样才能确定 F ，怎样才能确定全部的 F
	 * 比如： N = 1 层楼
	 * 在 1 层扔，碎了，因为楼层高于 F 才会碎，所以 F < 1 。又因为 0 <= F <= N ，所以能确定 F = 0
	 * 在 1 层扔，没碎，因为从 F 楼层或比它低的楼层落下的鸡蛋都不会碎，所以 F >= 1 。又因为 0 <= F <= N ，所以能确定 F = 1
	 * 再比如： N = 2 层楼
	 * 在 1 层扔，碎了，F < 1，所以确定 F = 0
	 * 在 1 层扔，没碎，但在 2 层扔，碎了， F >= 1 && F < 2，所以确定 F = 1
	 * 在 2 层扔，没碎，F >= 2，所以确定 F = 2
	 * 4、如果只有一个蛋
	 * 如果唯一的 1 个蛋碎了，就无法继续测试了
	 * 如果从中间开始测，万一蛋碎了，连 1 个 F 都无法确定
	 * 只能从低到高，一层一层的判断
	 * 所以有 T 次机会，只可以确定出 T + 1 个 F
	 * 5、如果只有一次机会
	 * 这个好理解，只有 1 次机会，就算有很多蛋也派不上用场，所以等同于只有 1 个蛋，并且扔一次，根据上边的例子，只能确定 2 个 F
	 * 也就是只能确定 T(T=1) + 1 个 F
	 * 6、计算能确定 F 的个数
	 * 如果只有 1 个蛋，或只有 1 次机会时，只可以确定出 T + 1 个 F
	 * 其他情况时，递归。【蛋碎了减 1 个，机会减 1 次】 + 【蛋没碎，机会减 1 次】
	 * 
	 */
	public int superEggDrop(int k, int n) {
        int T = 1;//机会次数从1开始
        while(calculateF(k,T) < n + 1) T++;
        return T;//返回最小的T
    }
	//k个蛋，T机会，返回能确定几个F
    public int calculateF(int k,int T){
        if(k == 1 || T == 1) return T + 1;
        return calculateF(k - 1,T - 1) + calculateF(k,T - 1);
    }
}
